#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

int Init(Graph *graph)
{
	graph->MaxVertex = Default_Vertex_Size;
	graph->NumVertex = graph->NumEdge = 0;
	graph->VertexList = malloc(sizeof(datatype) * graph->MaxVertex);
	// graph->VertexList = calloc(Default_Vertex_Size, sizeof(datatype));
	if (graph->VertexList == NULL)
		return -1;
	graph->Edge = malloc(sizeof(int *) * graph->MaxVertex);
	if (graph->VertexList == NULL)
		return -2;
	for (int i = 0; i < graph->MaxVertex; i++)
	{
		graph->Edge[i] = malloc(sizeof(int) * graph->MaxVertex);
		if (graph->Edge[i] == NULL)
			return -3;
	}
	for (int i = 0; i < graph->MaxVertex; i++)
	{
		for (int j = 0; j < graph->MaxVertex; j++)
		{
			if (i == j)
				graph->Edge[i][j] = 0;
			else
				graph->Edge[i][j] = MAX_COST;
		}
	}
	return 0;
}

void Show(Graph *graph)
{
	printf("   ");
	for (int i = 0; i < graph->NumVertex; i++)
		printf("%c  ", graph->VertexList[i]);
	printf("\n");
	for (int i = 0; i < graph->NumVertex; i++)
	{
		printf("%c  ", graph->VertexList[i]);
		for (int j = 0; j < graph->NumVertex; j++)
		{
			if (graph->Edge[i][j] == MAX_COST)
				printf("%2c ", '@'); //约定@在输出时表示无穷大
			else
				printf("%2d ", graph->Edge[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

int InsertVertex(Graph *graph, datatype vertex)
{
	if (graph->NumVertex == graph->MaxVertex)
		return -1;
	graph->VertexList[graph->NumVertex++] = vertex;
	return 0;
}

int GetVertexPosition(Graph *graph, datatype vertex)
{
	for (int i = 0; i < graph->NumVertex; i++)
	{
		if (graph->VertexList[i] == vertex)
			return i;
	}
	return -1;
}

int InsertEdge(Graph *graph, datatype vertex1, datatype vertex2, type_weight cost)
{
	int p1 = GetVertexPosition(graph, vertex1);
	int p2 = GetVertexPosition(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	if (p1 == p2)
		return -2;
	graph->Edge[p1][p2] = cost;
	++graph->NumEdge;
	return 0;
}

int RemoveVertex1(Graph *graph, datatype vertex)
{
	int pos = GetVertexPosition(graph, vertex);
	if (pos == -1)
		return -1;
	//顶点列表中的删除顶点后的顶点前移
	for (int i = pos; i < graph->NumVertex - 1; ++i)
		graph->VertexList[i] = graph->VertexList[i + 1];
	//统计删除顶点连接的边数
	int numedge = 0;
	for (int i = 0; i < graph->NumVertex; ++i)
	{
		if (graph->Edge[pos][i])
			numedge++;
	}
	// numedge += graph->Edge[pos][i];
	//行上移
	for (int i = pos; i < graph->NumVertex - 1; ++i)
		for (int j = 0; j < graph->NumVertex; ++j)
			graph->Edge[i][j] = graph->Edge[i + 1][j];
	//列上移
	for (int i = pos; i < graph->NumVertex; ++i)
		for (int j = 0; j < graph->NumVertex; ++j)
			graph->Edge[j][i] = graph->Edge[j][i + 1];
	--graph->NumVertex;
	graph->NumEdge -= numedge;
	return 0;
}

int RemoveVertex2(Graph *graph, datatype vertex)
{
	int pos = GetVertexPosition(graph, vertex);
	if (pos == -1)
		return -1;
	int numedge = 0;
	for (int i = 0; i < graph->NumVertex; ++i)
		numedge += graph->Edge[pos][i];
	//修改顶点列表
	graph->VertexList[pos] = graph->VertexList[graph->NumVertex - 1];
	//行覆盖
	for (int i = 0; i < graph->NumVertex; i++)
		graph->Edge[pos][i] = graph->Edge[graph->NumVertex - 1][i];
	//列覆盖
	for (int i = 0; i < graph->NumVertex; i++)
		graph->Edge[i][pos] = graph->Edge[i][graph->NumVertex - 1];
	--graph->NumVertex;
	graph->NumEdge -= numedge;
	return 0;
}

int RemoveEdge(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosition(graph, vertex1);
	int p2 = GetVertexPosition(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	if (graph->Edge[p1][p2] == 0) //本来就没有边
		return -2;
	graph->Edge[p1][p2] = graph->Edge[p2][p1] = 0;
	--graph->NumEdge;
	return 0;
}

int GetFirstNeighbor(Graph *graph, datatype vertex)
{
	int pos = GetVertexPosition(graph, vertex);
	if (pos == -1)
		return -1;
	for (int i = 0; i < graph->NumVertex; ++i)
	{
		if (graph->Edge[pos][i] != 0 && graph->Edge[pos][i] != MAX_COST)
			return i;
	}
	return -2;
}

int GetNextNeighbor(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosition(graph, vertex1);
	int p2 = GetVertexPosition(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	for (int i = p2 + 1; i < graph->NumVertex; i++)
	{
		if (graph->Edge[p1][i] != 0 && graph->Edge[p1][i] != MAX_COST)
			return i; //正确返回结果
	}
	return -1;
}

void DestoryGraph(Graph *graph)
{
	free(graph->VertexList);
	graph->VertexList = NULL;
	for (int i = 0; i < graph->MaxVertex; i++)
		free(graph->Edge[i]);
	free(graph->Edge);
	graph->Edge = NULL;
	graph->MaxVertex = graph->NumVertex = graph->NumEdge = 0;
}

int ShortestPath(Graph *graph, char vertex)
{
	int n = graph->NumVertex;

	int *dist = malloc(sizeof(int) * n);
	int *path = malloc(sizeof(int) * n);
	int *S = malloc(sizeof(int) * n);
	if (dist == NULL || path == NULL || S == NULL)
		return -1;
	int v = GetVertexPosition(graph, vertex);
	for (int i = 0; i < n; i++)
	{
		dist[i] = graph->Edge[v][i];
		S[i] = 0; //开始没有任何顶点加入
		if (i != v && dist[i] < MAX_COST)
			path[i] = v;
		else
			path[i] = -1;
	}

	S[v] = 1;			// v结点加入访问集合
	for (int i = 0; i < n - 1; i++) //剩余n-1个结点需要计算
	{
		int min = MAX_COST;
		int u = v;
		for (int j = 0; j < n; j++)
		{
			if (!S[j] && dist[j] < min)
			{
				u = j;
				min = dist[j];
			}
		}
		S[u] = 1;
		//更新起始顶点到各结点的距离
		for (int k = 0; k < n; k++)
		{
			int w = graph->Edge[u][k];
			if (!S[k] && w < MAX_COST && dist[u] + w < dist[k])
			{
				dist[k] = dist[u] + w;
				path[k] = u;
			}
		}
		//============================================================
		//更新起始顶点到各结点的距离另一种实现，即只看新加入结点的邻接结点
		// int w = GetFirstNeighbor(graph, graph->VertexList[u]);
		// while (w != -1)
		//{
		//     int weight = graph->Edge[u][w];
		//     if (!S[w] && weight < MAX_COST && dist[u] + weight < dist[w])
		//     {
		//          dist[w] = dist[u] + weight;
		//          path[w] = u;
		//     }
		//     w = GetNextNeighbor(graph, graph->VertexList[u], graph->VertexList[w]);
		//}
		//============================================================
	}

	int *print = malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
	{
		int k = 0;
		if (i != v)
		{
			int j = i;
			while (j != v)
			{
				j = path[j];
				print[k++] = j;
			}
		}
		while (k)
			printf("%c-->", graph->VertexList[print[--k]]);
		printf("%c:cost = %d\n", graph->VertexList[i], dist[i]);
	}

	free(dist);
	free(path);
	free(S);
	free(print);

	return 0;
}
